package util.parser;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

//表达式的二叉树类 非叶子节点一定是运算符(OPERATOR) 叶子结点一定是运算数(OPERAND)
public class BinaryTree {
    String root;
    BinaryTree left, right;
    boolean shouldBraced = false;

    BinaryTree(String root) {
        this(root, null, null);
    }

    public BinaryTree(String root, BinaryTree left, BinaryTree right) {
        this.root = root;
        setLeft(left);
        setRight(right);
    }

    /**
     * 根据后缀表达式生成运算二叉树
     *
     * @param exp
     * @return
     */
    public static BinaryTree createBinaryTree(List<String> exp) {
        Stack<BinaryTree> S = new Stack<>();
        for (String tok : exp) {
            if (OperatorPriority.isNumber(tok)) {
                BinaryTree tree = new BinaryTree(tok);
                S.push(tree);
            } else {
                BinaryTree right = S.peek();
                S.pop();
                BinaryTree left = S.peek();
                S.pop();
                BinaryTree tree = new BinaryTree(tok, left, right);
                S.push(tree);
            }
        }
        return S.peek();
    }

    public static void main(String[] args) {
//        BinaryTree left = new BinaryTree("1");
//        BinaryTree right = new BinaryTree("5");
//        BinaryTree exp = new BinaryTree("+", left, right);
//        //exp.postVisit();
//        exp.midVisit();
        BinaryTree exp2 = BinaryTree.createBinaryTree(Arrays.asList("1 2 + 3 4 + *".split("\\s+")));
        // exp2.postVisit();
        // String result = exp2.midVisit();
        // System.out.println(result);
        StringBuffer buffer = new StringBuffer();
        exp2.midVisit(buffer);
        System.out.println(buffer);
    }

    boolean isLeaf() {
        return left == null && right == null;
    }

    void setLeft(BinaryTree left2) {
        this.left = left2;
        if (left != null && !left.isLeaf() && OperatorPriority.isLower(left.root, root)) {
            left.shouldBraced = true;
        }
    }

    void setRight(BinaryTree right2) {
        this.right = right2;
        if (right != null && !right.isLeaf() && OperatorPriority.isHigher(root, right.root)) {
            right.shouldBraced = true;
        }
    }

    void preVisit() {//根节点 前序左子树，前序右子树
        System.out.print(root + " ");
        if (left != null) {
            left.preVisit();
        }
        if (right != null) {
            right.preVisit();
        }
    }
    //version 1
//    String midVisit() {
//        String sLeft = "";
//        if (left != null)
//            sLeft = left.midVisit();
//        String sRight = "";
//        if(right!=null)
//            sRight = right.midVisit();
//
//        return "(" + sLeft + root + sRight + ")";
//    }

    void postVisit() {//后序左子树，后序右子树 根节点
        if (left != null) {
            left.postVisit();
        }
        if (right != null) {
            right.postVisit();
        }
        System.out.print(root + " ");
    }

    //version 0
    void midVisit() {//中序左子树，中序右子树 根节点
        System.out.print("(");
        if (left != null) {
            left.midVisit();
        }
        System.out.print(root);
        if (right != null) {
            right.midVisit();
        }
        System.out.print(")");
    }

    public void midVisit(StringBuffer buffer) {
        if (shouldBraced) {
            buffer.append("(");
        }
        if (left != null) {
            left.midVisit(buffer);
        }
        buffer.append(root);
        if (right != null) {
            right.midVisit(buffer);
        }
        if (shouldBraced) {
            buffer.append(")");
        }

    }

}
